package cn.edu.njust.alg.leetcode;

import java.util.Arrays;


/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_106_Construct_Binary_Tree_from_Postorder_and_Inorder_Traversal {

	public static TreeNode buildTree(int[] inorder, int[] postorder) {
		if (postorder.length == 0 || inorder.length == 0) {
			return null;
		}
		int i;
		int last = postorder.length - 1;
		TreeNode root = new TreeNode(postorder[last]);
		for (i = 0; i < inorder.length; i++) {
			if (inorder[i] == postorder[last]) {
				break;
			}
		}
//		System.out.println();
//		System.out.println("root: " + postorder[last]);
//		ArrayUtils.printArray(inorder);
//		ArrayUtils.printArray(postorder);
		int[] il = Arrays.copyOfRange(inorder, 0, i);
		int[] ir = Arrays.copyOfRange(inorder, i + 1, inorder.length);
		int lenl = il.length;
		int[] pl = Arrays.copyOfRange(postorder, 0, lenl);
		int[] pr = Arrays.copyOfRange(postorder, lenl, postorder.length - 1);
		root.left = buildTree(il, pl);
		root.right = buildTree(ir, pr);
		return root;
	}

	private static void pretravel(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.val + " ");
		pretravel(root.left);
		pretravel(root.right);
	}

	private static void intravel(TreeNode root) {
		if (root == null) {
			return;
		}
		pretravel(root.left);
		System.out.print(root.val + " ");
		pretravel(root.right);
	}

	private static void potravel(TreeNode root) {
		if (root == null) {
			return;
		}
		pretravel(root.left);
		pretravel(root.right);
		System.out.print(root.val + " ");
	}

	public static void main(String[] args) {
		//int[] pr = { 1, 2, 3, 4, 5, 7, 6 };
		int[] in = { 3, 2, 5, 7, 4, 6, 1 };
		int[] po = { 3, 7, 5, 6, 4, 2, 1 };
		TreeNode root = buildTree(in, po);
		pretravel(root);
		System.out.println();
		intravel(root);
		System.out.println();
		potravel(root);

		System.out.println();

	}

}
